dp

背包九讲问题

01 背包问题
完全背包问题
多重背包问题
混合背包问题
二维费用的背包问题
分组背包问题
背包问题求方案数
背包问题求方案路径
有依赖的背包问题

01背包

问题背景：有 n 件物品，每一件物品 i 对应一个体积 v[i] 和一个价值 w[i]，设有一个背包，体积为 V，在这个背包下能装下的价值的最大值是多少？

模板

最原始方法：

dp[i][j]定义：表示前 i 个物品，总体积是 j 的情况下，总价值最大是什么？
状态转移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j -v[i]] + w[i])
Max = dp[n][V]

优化

dp[i][j] 只跟上一层的外循环有关，所以根本没有必要使用二维数组，只需要使用一维数组即可，注意，使用一维数组的时候，内层循环需要从后向前遍历；
将 dp[0][j] 全部初始化为 0 ，则 dp[i][j] 就代表前 i 个物品，总体积小于等于 j 的最大总价值，故上文的Max = dp[V]，代表总体积小于等于 V 的最大总价值；
如果要求的总价值的前提是背包容量恰好是 V，则只需要将初始化的值改为 dp[0][0] = 0 ，dp[0][j] = - INF 即可。

最终模板

int[] dp = new int[V+1];
for(int i = 1;i <= n;i++){
	for(int j = V;j >= v[i];j--){
		dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
	}
}
return dp[V];

例题

leetcode第416题：分割等和子集

leetcode第494题目标和

416 题代码

public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum = sum + nums[i];
        }
        if(sum % 2 != 0 ) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for(int i = 1;i <= nums.length;i++){
            for(int j = target;j >= nums[i-1];j--){
                if(dp[target]) return true;
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        } 
        return false;
    }
}

494 题代码

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        // 正数集合 P，负数集合 T
        // P - T = target， P + T = sum
        // P = (sum + target) / 2
        // 即题目就是找 子集和的方法数
        // 典型的01背包问题求解方案数，只需要把初始化的值改动一下，还要把状态转移方程中的 max ---> sum
        int count = 0;
        for(int i = 0;i < nums.length;i++){
            count = count + nums[i];
        }
        if(count < S) return 0;
        if((S + count) % 2 != 0) return 0;
        int P = (S + count)/2;
        int[] dp = new int[P+1];
        dp[0] = 1; // 这里是第一个改动，因为例如二维数组中的dp[1][1] = dp[0][0] + dp[0][1],dp[0][1] = 0
        //此时要使得dp[1][1] = 1,则dp[0][0] = 1,这也符合常理，即0个数能找到和为0的方案为一种
        for(int i = 1;i <= nums.length;i++){
            for(int j = P;j >= nums[i-1];j--){
                dp[j] = dp[j] + dp[j - nums[i-1]];
            }
        }
        return dp[P];
    }
}

完全背包

相比 01 背包问题来说，这里的一件物品可以选不止一次

所以，这里的做法跟 01 背包只有一个不同，01背包的一维数组的方法中的内层循环是从后向前遍历，原因是其在循环第 i 个物品时要用到第 i-1个物品的对应的值，且要用到的值都没有被本次循环更新过，而这里恰恰相反，因为一次物品可以用多次，所以完全背包问题允许在循环第 i 个物品时提前更新要用到的值，具体˙证明可以使用数学归纳法。

模板

f[j] 表示总体积是 j 的情况下，最大价值是什么

int[] dp = new int[V+1];
// 注意内层循环是从前往后
for(int i = 0;i <= n;i++){
	for(int j = v[i];j <= V;j--){
		dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
	}
}
return dp[V];

多重背包问题 I

相比完全背包问题相比，就是每个物品多了一个数量的限制，类似于01背包，只不过那里的物品的数量为1，这里的数量是 s。

模板

// 初始化，f[i] = 0,i =0...n

int[] dp = new int[V+1];
for(int i = 1;i <= n;i++){
	for(int j = V;j >= 0;j--){
    // 和01背包唯一的区别
    for(int k = 1;k <= s && j >= k * v[i];k++){
      dp[j] = Math.max(dp[j],dp[j - v[i]*k] + w[i]*k);
    }
	}
}
return dp[V];

多重背包问题 II

其实就是对上面这个模板的优化，是对多重背包的二进制优化方法。最内层循环的意思其实就是把背包的每一次重复都当成一次新的物品，类似于打包的形式，比如第一个物品体积是 v，价值为 w，第二个物品就是 2v，价值为 2w，以此类推，但是这样分解的时间复杂度太高了，可以通过二进制优化方法，为什么呢？因为他们之间是互斥的，每次都会只选出一个来，是后面的分组背包的特殊情况，所以我们只需要找到能表示所有方案的物品就行，无需全部罗列都当成01背包的物品。比如现在的 s 为7，按照上面的方法，我们需要比较0、1、2、3、4、5、6、7这8个方案的最大值，但是其实我们可以用三位数就表示0、1、2、3、4、5、6、7，因为我们只需要从这8个方案中选取一个即可，所以三位数就可以表示所有，然后从中选取自己符合要求的就行，在这里我们可以选择1、2、4，就能表示 0 ~ 7 所有元素，如果 s 为 10，那么我们可以选取 1、2、4、3 ，3是如何来的呢，是

10 - （2^ 3 -1） 得来的，故就将线性复杂度变为 log2 复杂度了。

模板

int[] dp = new int[V+1];
for(int i = 1;i <= n;i++){
	for(int j = V;j >= 0;j--){
    for(int k = 1;k <= s;k = k * 2){
      s = s - k;
      // 把每个 k 对应的都变成 一种物品
      if(j >= k * v[i]) dp[j] = Math.max(dp[j],dp[j - k * v[i]] + k * w[i]);
    }
    //不等于0，说明有余数
    if(s != 0 && j >= s * v[i]) dp[j] = Math.max(dp[j],dp[j - s * v[i]] + s * w[i]);
  }
}

多重背包问题 III

这是对多重背包的再次优化，上文已经将最内层循环从 O(n) 降为了 O(logn)，这里可以运用单调队列将最内层循环的 O(n) 降成 O(1)。

完全背包问题转移图和多重背包一样。不过没有了物品个数限制，所以不是滑动窗口情况，不用单调队列。只保存一个最大值就可以。所以完全背包问题可以直接从前向后遍历，因为其只需要保存一个最大值。所以这里引入了单调队列之后，也维护了相同余数的最大值，故 j 也可以从前向后遍历。

思路：https://blog.csdn.net/qq_40679299/article/details/81978770

为何引入单调队列分析：https://www.cnblogs.com/DeepJay/p/12025225.html

代码和思路精简版：https://www.acwing.com/solution/acwing/content/6500/（主推这个）

模板

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 表示物品种类
        int n = scan.nextInt();
        // 表示 最大的容积
        int V = scan.nextInt();
        int[] dp = new int[V + 1];
        for (int i = 0; i < n; i++) {
            int v = scan.nextInt();
            int w = scan.nextInt();
            int s = scan.nextInt();
            int[] pre = Arrays.copyOf(dp,dp.length);
            // 遍历所有余数
            for (int j = 0; j < v; j++) {
                // 每个余数对应一个双端队列，实现单调队列
                LinkedList<Integer> queue = new LinkedList();
                for (int k = j; k <= V; k = k + v) {
                    // 1. 去除队尾不符合要求的，保证从大到小，如果前面数小则需要依次弹出
                    while (!queue.isEmpty() && pre[queue.peekLast()] - (queue.peekLast() - j) / v * w <= pre[k] - (k - j) / v * w) {
                        queue.pollLast();
                    }
                    // 2.判断当前队列中队首的值是否有效
                    if (!queue.isEmpty() && queue.peek() < k - s * v) {
                        queue.poll();
                    }
                    // 3.添加当前值对应的数组下标
                    queue.addLast(k);
                    // 4.拿到队首最大值
                    dp[k] = Math.max(dp[k], pre[queue.peek()] + (k - queue.peek()) / v * w);
                }

            }
        }
        System.out.println(dp[V]);
    }
}

例题

LeetCode 第 239 题：滑动窗口最大值

该题也是同样采用了单调队列的方式，官方题解的解法二就是采用双端队列实现单调队列。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
         if(nums == null || nums.length < 2) return nums;
        // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
        LinkedList<Integer> queue = new LinkedList();
        // 结果数组
        int[] result = new int[nums.length-k+1];
        // 遍历nums数组
        for(int i = 0;i < nums.length;i++){
            // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                queue.pollLast();
            }
            // 11 10 9 8 7 6 5
            // 判断当前队列中队首的值是否有效
            if(!queue.isEmpty() && queue.peek() <= i-k){
                queue.poll();
            }
            // 添加当前值对应的数组下标
            queue.addLast(i);
            // 当窗口长度第一次达到k后，开始保存当前窗口中最大值
            // 以后每走一步，就会保存一个最大值
            if(i+1 >= k){
                result[i+1-k] = nums[queue.peek()];
            }
        }
        return result;
    }
}

故总结一下，单调队列的模板为：

// 1.存入双端队列的是值的索引，第一步是先把队尾不符合要求的全部弹栈
// 2.然后判断队首是不是有不符合要求的，即不在窗口之中
// 3.将该值加入到队列中
// 4.获取到题目需要的东西，比如上文要取每个窗口的最大值，则将每个窗口的最大值存入数组即可

混合背包问题

混合背包，就是01背包，完全背包，多重背包结合在一起，方法就是分类判断，分类处理即可，非常简单，就不做过多解释了。

二维费用的背包问题

其实跟一维费用的背包问题如出一辙，就是多了一层循环，dp 由一维变成了二维，其他的跟一维的都是一样的。

分组背包问题

其实，分组背包前面已经讲过了，就是多重背包的一般化，就是因为多重背包的特殊，所以才会有两个优化的方法——-二进制优化 && 单调队列优化，所以对于分组背包问题，就只能采用 多重背包问题 I 的方法，三层循环。

背包问题求方案数

求方案数的关键就在于确定：在每一次循环中，是不是选了该数。求最优方案的方案数是通过判断该体积对应的价值的最大值有没有改变，从而判断是否选了该数，选了的话就把以前的方案数替换或者累加即可；求固定体积的方案数，就是直接dp[j] = dp[j] + dp[j - v[i]]，体积为 j 的就是等于选了和没选的总方案数（这个初始化是关键）。

求最优方案的方案数

这里只有一个比较大的改动，那就是添加了一个 cnt 数组来统计方案数。

这里初始化的时候，有两个方案，一个是，dp[0] = 0，dp[i] = 0; 另外一个是 dp[0] = 0，dp[i] = -INF。

方法一和方法二区别不大，跟 01背包一样，由于初始化的不同，导致最后的结果，一个直接取容量最大值即可，一个需要遍历，这里还是推荐方案一！

方法一

输入

总物品数：4 
最大容积：5
物品体积    价值
1 					2
2 					4
3 					4
4 					6

若初始化的值都为 0

	1	2	3	4	5
0	0	0	0	0	0
1	2	2	2	2	2
2	2	2	6	6	6
3	2	2	6	6	8
4	2	2	6	6	8

模板

定义两个数组，dp[j] 用来存储背包容积是 j 时的最佳方案的总价值，cnt[j] 用来存储容积为 j 时总价值为最佳的方案数；
先初始化 dp[0] = 0，dp[j] = -INF，很容易理解，容积为 0，自然价值就为 0 了，而要使得容积为 1、2…且没有数，则自然价值就不存在了，记为 -INF，再初始化所有的 cnt[j] = 1，因为背包里什么都不装对任何容积来说都是一种方案，在没有数的情况下自然就是最好的情况了；
在每次循环新物品时，先求得装新物品的总价值，然后与不装新物品对比，如果装了新物品的价值更大，那么就需要用 dp[j - v[i]] + w 更新 dp[j]，同时用 cnt[j - v[i]] 来更新 cnt[j]；
如果总价值相等，那么 cnt[j] = cnt[j] + cnt[j-v[i]]；
当然如果装了新物品还不如不装呢，那就啥也不用做了。

import java.util.Scanner;


public class Test {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        // 表示物品种类
        int n = scan.nextInt();
        // 表示 最大的容积
        int V = scan.nextInt();
        int[] dp = new int[V + 1];
        int[] cnt = new int[V + 1];
        for (int j = 0; j <= V; j++) {
            cnt[j] = 1;
        }
        for (int i = 0; i < n; i++) {
            int v = scan.nextInt();
            int w = scan.nextInt();
            for (int j = V; j >= v; j--) {
                int value = dp[j - v] + w;
                if (value > dp[j]) {
                    dp[j] = value;
                    cnt[j] = cnt[j - v];
                } else if (value == dp[j]) {
                    cnt[j] = cnt[j] + cnt[j - v];
                }
            }
        }
        System.out.println(cnt[V]);
    }
}

回看表格(括号内为 cnt 的值)

总物品数：4 
最大容积：5
物品体积    价值
1 					2
2 					4
3 					4
4 					6

	0	1	2	3	4	5
0	0(1)	0(1)	0(1)	0(1)	0(1)	0(1)
1	0(1)	2(1)	2(1)	2(1)	2(1)	2(1)
2	0(1)	2(1)	4(1)	6(1)	6(1)	6(1)
3	0(1)	2(1)	4(1)	6(1)	6(2)	8(1)
4	0(1)	2(1)	4(1)	6(1)	6(3)	8(2)

再来一个示例

总物品数：4 
最大容积：5
物品体积    价值
2 					4
2 					4
3 					4
4 					6

	0	1	2	3	4	5
0	0(1)	0(1)	0(1)	0(1)	0(1)	0(1)
1	0(1)	0(1)	4(1)	4(1)	4(1)	4(1)
2	0(1)	0(1)	4(2)	4(2)	8(1)	8(1)
3	0(1)	0(1)	4(2)	4(3)	8(1)	8(3)
4	0(1)	0(1)	4(2)	4(3)	8(1)	8(3)

套用上述模板，实现 LeetCode 494题

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int count = 0;
        for(int i = 0;i < nums.length;i++){
            count = count + nums[i];
        }
        if(count < S) return 0;
        if((S + count) % 2 != 0) return 0;
        int V = (S + count)/2;
        int[] dp = new int[V + 1];
        int[] cnt = new int[V + 1];
        for (int j = 0; j <= V; j++) {
            cnt[j] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];
            for (int j = V; j >= v; j--) {
                int value = dp[j - v] + v;
                if (value > dp[j]) {
                    dp[j] = value;
                    cnt[j] = cnt[j - v];
                } else if (value == dp[j]) {
                    cnt[j] = cnt[j] + cnt[j - v];
                }
            }
        }
        return cnt[V];
    }
}

方法二

若初始化的值不都为 0,用上面的示例

总物品数：4 
最大容积：5
物品体积    价值
2 					4
2 					4
3 					4
4 					6

	0	1	2	3	4	5
0	0(1)	-INF(1)	-INF(1)	-INF(1)	-INF(1)	-INF(1)
1	0(1)	-INF(1)	4(1)	-INF(1)	-INF(1)	-INF(1)
2	0(1)	-INF(1)	4(2)	-INF(2)	8(1)	-INF(1)
3	0(1)	-INF(1)	4(2)	4(1)	8(1)	8(2)
4	0(1)	-INF(1)	4(2)	4(1)	8(1)	8(2)

模板

import java.util.Scanner;


public class Test {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int ma = (int) (Math.pow(10,9) + 7);
        // 表示物品种类
        int n = scan.nextInt();
        // 表示 最大的容积
        int V = scan.nextInt();
        int[] dp = new int[V + 1];
        int[] cnt = new int[V + 1];
        for (int j = 0; j <= V; j++) {
            cnt[j] = 1;
            dp[j] = Integer.MIN_VALUE;
        }
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int v = scan.nextInt();
            int w = scan.nextInt();
            for (int j = V; j >= v; j--) {
                int value = dp[j - v] + w;
                if (value > dp[j]) {
                    dp[j] = value;
                    cnt[j] = cnt[j - v];
                } else if (value == dp[j]) {
                    cnt[j] = cnt[j] + cnt[j - v];
                }
            }
        }
        int max = Integer.MIN_VALUE;
        int count = 0;
        for(int i = 0;i <= V;i++){
            max = Math.max(dp[i],max);
        }
        for(int i = 0;i <= V;i++){
            if(dp[i] == max){
                count+=cnt[i];
            }
        }
        System.out.println(count);
    }
}

思路一模一样…就是头和尾复杂了一下，所以感觉没啥子必要…

求背包装至指定容量的方案数

这个非常简单了，就是上面的特殊化例子，也就是把循环到的该数的容量作为价值，然后计算指定价值的方案数，这是一般化的做法，但是既然谈到特殊化，也就是容量和价值相等，那自然可以采用更简单的方法去处理了。

初始化 dp[0] = 1，代表 0 容量的背包的方案为1，其他都为0；
dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]]，很好理解了，就不做解释了。

示例就是 LeetCode 494 题。

背包问题求方案路径

如果没有要求得到按字典顺序最小的方案路径的话，就可以直接按01背包的方法去做(由于要记录方案路径，所以不能使用滚动数组，需要用到每一轮的方案，所以需要改为二维数组)，然后在遍历的时候，判断 f[i][j]是否和 f[i-1][j-v[i]] + w[i] 相等，如果相等说明用到了该个物品，加入方案路径中即可。

如果要求是得到最小的方案路径的话，则需要将方案从末尾遍历到开始，得到最佳方案后，再从前向后寻找方案路径。

模板

int[][] dp = new int[n+1][V+1];
for(int i = n;i >= 1;i--){
  //  二维的话内层循环就无所谓是从前往后还是从后往前了
	for(int j = V;j >= v[i];j--){
		dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j - v[i]] + w[i]);
	}
}
int vol = m;
for(int i = 1;i <= n;i++){
	if(f[i][vol] == f[i+1][vol-v[i]] + w[i]){
		// 将该方案加入
		System.out.println(i);
		vol = vol - v[i];
	}
}

有依赖的背包问题（我暂时没复习！）

这应该是背包问题里面最难的一类了，是用树形 dp + 分组背包问题的思路去解决。

https://www.acwing.com/solution/acwing/content/8316/

更多见视频：https://www.bilibili.com/video/av33930433/?p=2、https://www.bilibili.com/video/av34467850/?p=2（这个视频是从第 12 分钟开始讲背包 9 讲后面的 3 讲）

训练地址：https://www.acwing.com/problem/content/2/

更详细的背包九讲问题：已经下载到本地了，崔添翼的 pdf——> 本地文件名字叫背包问题九讲

链表

热题 100：

2. 两数相加

19. 删除链表的倒数第N个节点

21. 合并两个有序链表

23. 合并 K 个排序链表

25. K 个一组翻转链表

141. 环形链表

142. 环形链表 II

148. 排序链表

160. 相交链表

206. 反转链表

234. 回文链表

剑指 offer：

18. 删除链表的节点

22. 删除倒数第 k 个节点

24. 反转链表

35. 复杂链表的复制

52. 两个链表的第一个公共节点

相关题目

（热题100）

两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 首先比较位数，两个同时向后遍历，当 cur.next == null 时说明有一个已经到了最高位
        // 按照逆序的方式存储，其实是将题目变简单了。因为我们在计算两数相加时，是先算低位，再进位给高位
        // 逆序的话刚好就符合这种运算规则

        // 头结点
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        // 定义一个进位
        int quo = 0;
        while(l1 != null || l2 != null || quo != 0){
            int t = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + quo;
            quo = t/10;
            t = t % 10;
            cur.next = new ListNode(t);
            cur = cur.next;
            l1 = l1 == null ? l1 : l1.next;
            l2 = l2 == null ? l2 : l2.next;
        }
        return res.next;
    }
}

拓展，链表正序存储数字，如何计算？

双端队列

public class addTwoNumbers {
    public static void main(String[] args) {
        addTwoNumbers addTwoNumbers = new addTwoNumbers();
        ListNode list1 = new ListNode(9);
//        list1.next = new ListNode(4);
//        list1.next.next = new ListNode(3);
        ListNode list2 = new ListNode(5);
        list2.next = new ListNode(6);
        list2.next.next = new ListNode(4);
        // 9 + 564 = 573
        // 243 + 564 = 807
        ListNode listNode = addTwoNumbers.addTwoNumbers(list1,list2);
        System.out.println(listNode.val + "----->" + listNode.next.val + "------>" + listNode.next.next.val);

    }
    // 方法一：用双端队列实现
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 想法是使用两个双端队列，先将数都从队尾进队，当某个数 位数不够时，用0加到队首
        // 计算是都从队尾出
        // 出队后再用栈接收一下
        LinkedList<Integer> deque_l1 = new LinkedList<>();
        LinkedList<Integer> deque_l2 = new LinkedList<>();
        while(l1 != null){
            deque_l1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            deque_l2.push(l2.val);
            l2 = l2.next;
        }
        int deq1_len = deque_l1.size();
        int deq2_len = deque_l2.size();
        if(deq1_len > deq2_len){
            for(int i = 1;i <= deq1_len - deq2_len;i++){
                deque_l2.addLast(0);
            }
        }
        else if(deq2_len > deq1_len){
            for(int i = 1;i <= deq2_len - deq1_len;i++){
                deque_l1.addLast(0);
            }
        }
        Stack<Integer> stack = new Stack();
        int quo = 0;
        while (deque_l1.size() != 0){
            int sum = deque_l1.pop() + deque_l2.pop() + quo;
            stack.push(sum % 10);
            quo = sum/10;
        }

        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while(!stack.isEmpty()){
            cur.next = new ListNode(stack.pop());
            cur = cur.next;
        }
        return  res.next;
    }
}

将链表反转，然后计算，最后再反转回来

public ListNode addTwoNumbers2(ListNode l1, ListNode l2){
        ListNode reverse_l1 = reverseList(l1);
        ListNode reverse_l2 = reverseList(l2);
        ListNode tmp = addTwoNumbers(reverse_l1,reverse_l2);
        ListNode listNode = reverseList(tmp);
        return listNode;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 头结点
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        // 定义一个进位
        int quo = 0;
        while(l1 != null || l2 != null || quo != 0){
            int t = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + quo;
            quo = t/10;
            t = t % 10;
            cur.next = new ListNode(t);
            cur = cur.next;
            l1 = l1 == null ? l1 : l1.next;
            l2 = l2 == null ? l2 : l2.next;
        }
        return res.next;
    }
    public ListNode reverseList(ListNode head) {
        // 如果当前要反转的节点为 null 或者反转链表为 null
        // head.next 为 null，即反转链表的尾结点不存在，即反转链表不存在
        if (head == null || head.next == null) return head;
        // 节点 p 其实就是反转链表的头节点
        ListNode p = reverseList(head.next);
        // 我们将反转链表的尾结点（head.next）的 next 指向当前即将反转的节点
        head.next.next = head;
        // 然后让当前节点变成反转链表的尾结点
        head.next = null;
        // 返回反转链表的头结点
        return p;
    }

删除链表的倒数第 N 个节点

利用先后指针，常用的双指针技巧之一：快慢指针、先后指针、滑动窗口。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        //可能会把头结点给删了，所以可以建个哑巴节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode front = dummy;
        ListNode back = dummy;

        for(int i = 1;i <= n;i++){
            front = front.next;
        }
        while(front.next != null){
            front = front.next;
            back = back.next;
        }
        back.next = back.next.next;
        return dummy.next;
    }
}

合并两个有序链表

这个貌似没什么难度，稍微注意一点细节就行了

迭代

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode dummy = res;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                res.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            else{
                res.next = new ListNode(l1.val);
                l1 = l1.next;

            }
            res = res.next;
        }
        if(l1 == null) res.next = l2;
        else res.next = l1;
        return dummy.next;
    }
}

递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

合并 K 个排序链表

优先级队列

class Solution {
    // 方法一：直接使用优先级队列
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue((Comparator<ListNode>) (o1, o2) -> o1.val - o2.val);
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        if(lists.length == 0) return null;
        for(ListNode list : lists){
            if(list == null) continue;
            priorityQueue.add(list);
        } 
        while(!priorityQueue.isEmpty()){
            ListNode min = priorityQueue.poll();
            cur.next = min;
            if(min.next != null) priorityQueue.add(min.next);
            cur = cur.next;
        }
        return  dummy.next;
    }
}

归并

class Solution {
    /**
     * 方法二 归并排序
     * 要注意跟数组的区别
     * 数组可以直接通过下标索引，所以在归并时无需返回值，但链表必须在每次归并时提供链表头结点，否则无法归并
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        return merge(lists,0,lists.length-1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if(left == right) return lists[left];
        int mid = left + (right - left)/2;
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);
        return mergeTwoLists(l1,l2);

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

暴力法

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        for(int i = 1;i < lists.length;i++){
            lists[i] = mergeTwoLists(lists[i],lists[i-1]);
        }
        return lists[lists.length-1];
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

环形链表

Set集合存储

public class Solution {
    //用 Set 来存储，如果出现了，则说明有环，否则就无环
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while(head != null){
            if(set.add(head)){
                head = head.next;
            }
            else {
                return true;
            }
        }
        return false;
    }
}

快慢指针

public class Solution {
    //用 快慢指针
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}

环形链表 II

典型的快慢指针解决此问题

起点是哑巴节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        // 起点很重要，这个跟环形链表 I 不一样
        // 一定要注意这个细节
        // 因为第二次相遇得 fast 和 slow 走的距离一样
        ListNode slow = head;
        ListNode fast = head.next;
        while (true) {
            if(fast == null || fast.next == null) return null;
            if (slow == fast) {
                break;
            };
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = head;
        fast = fast.next;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

起点是头结点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        // 起点很重要，这个跟环形链表 I 不一样
        // 一定要注意这个细节
        // 因为第二次相遇得 fast 和 slow 走的距离一样
        ListNode slow = head;
        ListNode fast = head;
        while (true) {
            if(fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
            // 注意这里判断的地方跟上面略有不同
            if (slow == fast) {
                break;
            };
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

排序链表【难点哈！】

不符合空间复杂度，直接利用列表

class Solution {
    public ListNode sortList(ListNode head) {
        List<Integer> arrayList = new ArrayList();
        while(head != null){
            arrayList.add(head.val);
            head = head.next;
        }
        Collections.sort(arrayList);
        return ListToLinked(arrayList);
    }
    public ListNode ListToLinked(List<Integer> arrayList){
        if(arrayList.size() == 0) return null;
        ListNode node = new ListNode(arrayList.get(0));
        // 注意这个 arrayList.subList()的返回值是 List
        // 并且方法中的参数是[fromIndex,toIndex)，左闭右开。
        node.next = ListToLinked(arrayList.subList(1,arrayList.size()));
        return node;
    }
}

归并排序，并且在合并时采用递归，空间复杂度降为 O(logn)，这个就跟合并 K 个有序链表是一样的思路，只不过这里就相当于 K 个链表长度为 1 的链表进行归并，并且还不能通过数组索引到 mid，只能是通过快慢指针找到 mid。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

归并排序，合并时不采用递归，空间复杂度为常数

还未研读！

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode h, h1, h2, pre, res;
        h = head;
        int length = 0, intv = 1;
        while (h != null) {
            h = h.next;
            length++;
        }
        res = new ListNode(0);
        res.next = head;
        while (intv < length) {
            pre = res;
            h = res.next;
            while (h != null) {
                int i = intv;
                h1 = h;
                while (i > 0 && h != null) {
                    h = h.next;
                    i--;
                }
                if (i > 0) break;
                i = intv;
                h2 = h;
                while (i > 0 && h != null) {
                    h = h.next;
                    i--;
                }
                int c1 = intv, c2 = intv - i;
                while (c1 > 0 && c2 > 0) {
                    if (h1.val < h2.val) {
                        pre.next = h1;
                        h1 = h1.next;
                        c1--;
                    } else {
                        pre.next = h2;
                        h2 = h2.next;
                        c2--;
                    }
                    pre = pre.next;
                }
                pre.next = c1 == 0 ? h2 : h1;
                while (c1 > 0 || c2 > 0) {
                    pre = pre.next;
                    c1--;
                    c2--;
                }
                pre.next = h;
            }
            intv *= 2;
        }
        return res.next;
    }
}

相交链表

走相同距离的路，必定在相交点相遇。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != p2){
            p1 = (p1 == null ? headB : p1.next);
            p2 = (p2 == null ? headA : p2.next);
        }
        return p1;
    }
}

反转链表

递归(这 5 步得牢记于心)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

非递归(每一步就只是把下一次该反转的节点记住即可，然后把curr.next换成pre就行了)

class Solution {
    public ListNode reverseList(ListNode head) {
        // 利用三个指针，分别存储遍历的该节点，前节点和后节点
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            // 只需要保存下一次反转的节点就行了
            ListNode nextTemp = cur.next;
            cur.next = pre;
            // 下一次反转
            pre = cur;
            cur = nextTemp;
        }
        return pre;
    }
}

K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路：

步骤分解:

链表分区为已翻转部分+待翻转部分+未翻转部分
每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
经过k轮循环，end 到达末尾，记录待翻转链表的后继 next = end.next
翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环
特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
时间复杂度为 O(n*K) ，最好的情况为 O(n)，最差的情况未 O(n^2)
空间复杂度为 O(1)，除了几个必须的节点指针外，我们并没有占用其他空间

作者：reals
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) {
                break;
            }
            // start 记录即将翻转的链表的前一个节点
            ListNode start = pre.next;
            // next 记录即将翻转的链表的后一个节点
            ListNode next = end.next;
            // 翻转链表前的准备，因为一个链表翻转，其最后的 end.next 是指向的空
            end.next = null;
            // 翻转后，接上前面的链表节点
            pre.next = reverse(start);
            // 此时的 start 的 next 在reverse 之后是指向空的，所以我们要接上后面的
            start.next = next;
            // 然后开始下一次翻转
            pre = start;
            end = pre;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

}

思考：如果最后一段小于 k 的链表也需要翻转呢？如何做？

很简单，只需要加一步，如果最后一段需要翻转，直接处理和前面的链表的连接就可以了，其他的都不需要。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) {
                pre.next = reverse(pre.next);
                break;
            }
            // start 记录即将翻转的链表的前一个节点
            ListNode start = pre.next;
            // next 记录即将翻转的链表的后一个节点
            ListNode next = end.next;
            // 翻转链表前的准备，因为一个链表翻转，其最后的 end.next 是指向的空
            end.next = null;
            // 翻转后，接上前面的链表节点
            pre.next = reverse(start);
            // 此时的 start 的 next 在reverse 之后是指向空的，所以我们要接上后面的
            start.next = next;
            // 然后开始下一次翻转
            pre = start;
            end = pre;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

回文链表

先利用快慢指针找到中点，然后反转前半部分，然后比对即可

class Solution {
    // 反转前半部分
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 1 2 3 4 此时 fast 会为 null ，slow 会为 3
        // 1 2 3 4 5 此时 fast.next 会为 null，slow 会为 3
        // 也就是 不论是奇数还是偶数，slow 都会是后半部分的第一个数

        // 反转前半部分
        ListNode pre = null;
        ListNode cur = head;
        while(cur != slow){
            ListNode nextTemp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextTemp;
        }
        if(fast != null){
            slow = slow.next;
        }
        while(pre != null){
            if(pre.val != slow.val) return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;     
    }
}

可以优化一下，直接在快慢指针找中点的同时进行翻转

class Solution {
        // 反转前半部分
        public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode fast = head;
        ListNode cur = head, pre = null;
        while(fast != null && fast.next != null) {
           // 这里的 cur 指针就是 slow 指针，充当了两个作用
           // 一个是快慢指针找中点，一个是反转链表，因为 cur 也是每轮循环走一步
           fast = fast.next.next;
           ListNode nextTemp = cur.next;
           cur.next = pre;
           pre = cur;
           cur = nextTemp;
        }
        if(fast != null) {
            cur = cur.next;
        }
        while(pre != null) {
            if(pre.val != cur.val) return false;
            pre = pre.next;
            cur = cur.next;
        }
        return true;
    }
}

链表转列表，然后比对

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

(剑指offer)

删除链表中的节点

找一个牺牲者

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        // 这个方法叫找一个牺牲者
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head;
        ListNode pre = dummy;
        while(cur != null && cur.next != null){
            if(cur.val == val){
                cur.val = cur.next.val;
                cur.next = cur.next.next;
                return dummy.next;
            }
            pre = cur;
            cur = cur.next;
        }
        if(cur.next == null){
            pre.next = null;
        }
        return dummy.next;
    }
}

直接判断下一个是不是

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        dummy.next = head;
        while(pre.next != null){
            if(pre.next.val == val){
                pre.next = pre.next.next;
                return dummy.next;
            }
            pre = pre.next;
        }
        return dummy.next;
    }
}

链表中的倒数第K个节点

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //使用前后指针
        ListNode back = head;
        ListNode front = head;
        for(int i = 0;i < k;i++){
            front = front.next;
        }
        while(front != null){
            back = back.next;
            front = front.next;
        }
        return back;
    }
}

复制带随即指针的链表【难点哈】

HashMap 复制

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node, Node> lookup = new HashMap<>();
        Node node = head;
        while (node != null){
            lookup.put(node, new Node(node.val, null, null));
            node = node.next;
        }
        node = head;
        while (node != null){
            lookup.get(node).next = lookup.get(node.next);
            lookup.get(node).random = lookup.get(node.random);
            node = node.next;
        }
        return lookup.get(head);
    }
}

O(1) 空间复杂度

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 复制
        while(cur != null){
            Node tmp = cur.next;
            cur.next = new Node(cur.val,null,null);
            cur.next.next = tmp;
            cur = tmp;
        }

        // 置随机指针
        cur = head;
        while(cur != null){
            // 易错点，别忘了判断
            if(cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        // 拆分
        cur = head;
        Node copy_head = head.next;
        Node copy_cur = copy_head;
        while(copy_cur.next != null){
            cur.next = cur.next.next;
            cur = cur.next;
            // 注意哦，这里while循环必须是 copy_cur.next != null
            // 原因是下面这行代码，如果是 copy_cur != null，那下面就会空指针异常
            copy_cur.next = copy_cur.next.next;
            copy_cur = copy_cur.next;
        }

        //别忘了给 cur 最后 加 null
        cur.next = null;
        return copy_head;

    }
}

dp